package com.xxwy.sort.nlogn;

import com.xxwy.sort.Sort;
import com.xxwy.sort.SortHelper;

/**
 * @author xxwy
 */
public class HeapSort implements Sort {
    @Override
    public void sort(int[] array, int n) {
        //heapify,最大的元素就在array[0]
        for (int i = (n - 2) / 2; i >= 0; i--) {
            siftDown(array, n, i);
        }

        for (int i = n - 1; i > 0; i--) {
            SortHelper.swap(array, 0, i);
            siftDown(array, i, 0);
        }

    }

    /**
     * @param array
     * @param n     ： 需要siftdown数组的个数
     * @param l     : 头位置
     */
    private void siftDown(int[] array, int n, int l) {
        //(l * 2 + 1) < n 这句话表示，这个头位置有孩子
        while ((l * 2 + 1) < n) {
            int childMax = l * 2 + 1;
            if (childMax + 1 < n  && array[childMax] < array[childMax + 1]){
                childMax++;
            }
            if (array[l] >= array[childMax]) {
                break;
            }
            SortHelper.swap(array, l, childMax);
            l = childMax;
        }
    }
}
